public class MinDistance {
    // leetcode 编辑距离
    // https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-100-liked
    public int minDistance(String word1, String word2) {
        // 对于两个字符串的操作大致可以分为六种
        // 1. 删除字符串A的第i个字符
        // 2. 删除字符串B的第j个字符
        // 3. 对于字符串A，增加字符串B的第j个字符
        // 4. 对于字符串B，增加字符串A的第i个字符
        // 5. 替换字符串A的第i个字符为字符串B的第j个字符
        // 6. 替换字符串B的第j个字符为字符串A的第i和字符
        // 但是在字符串A中删除字符和在字符串B中增加字符是等价的
        // 所以上面的六种操作就可以合并为三种操作
        // 1. 在字符串A中增加字符
        // 2. 在字符串B中增加字符
        // 3. 修改字符串A中的字符
        int len1 = word1.length(), len2 = word2.length();
        // dp[i][j]表示字符串A[0,i]和字符串B[0,j]的最短编辑距离
        int[][] dp = new int[len1+1][len2+1];
        // 对于上面的三种情况，分别对应
        // 1. dp[i][j-1] 2. dp[i-1][j] 3. dp[i-1][j-1]
        // 然后dp[i][j]就是三种情况的最小值
        // 初始化：当word1为空字符串的时候，那么最短编辑距离就是word2对应的长度，反之亦然
        for (int j = 1; j <= len2; j++) dp[0][j] = j;
        for (int i = 1; i <= len1; i++) dp[i][0] = i;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                // 如果word1第i个字符等于word2的第j个字符，那么dp[i][j] = dp[i-1][j-1]
                if (word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                else {
                    dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
}
